package com.julius.design.suanfa.array;

/**
 * @author julius
 * @date 2021-11-03 下午 3:27
 * <p>
 *
 * </p>
 */
public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        //有序数组 查找两个数字相加 == target
        int i = 0;
        int [] ans = new int[2];
        //活用二分查找

        while(i < nums.length){
            ans[0] = nums[i];
            if(target - ans[0] == 0){
                ans[1] = nums[i];
                return ans;
            }
            int k = binary(nums,i+1,nums.length-1,target-ans[0]);
            if(k == -1){
                i++;
                continue;
            }
            ans[1] = k;
            return ans;
        }
        return ans;
    }

    /**
     二分查找
     */
    public static int binary(int[] nums,int start,int end,int target){



        while(start <= end){
            int mid = start+(end-start)/2;
            if(nums[mid] == target){
                return target;
            }
            if(nums[mid] > target){
                end = mid-1;
            }else{
                start = mid+1;
            }
        }

        return -1;
    }

    public int[] twoSum2(int[] nums, int target) {
        //快慢指针 ，前后指针
        //[2,7,11,15] 22

        int i = 0,j = nums.length -1;

        int[] ans = new int[2];
        while(i<j){
            if(nums[i]+nums[j] == target){
                ans[0] = nums[i];
                ans[1] = nums[j];
                return ans;
            }
            if(nums[i]+nums[j] > target){
                j--;
            }
            if(nums[i]+nums[j] < target){
                i++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{14,15,16,22,53,60};
        int[] ints = twoSum(nums, 76);
        System.out.println(ints[0]+"--------"+ints[1]);
    }

}
